Amiga Format CD 40/Amiga Format CD40 (1999-05-11)(Future Publishing)(GB)(Track 1 of 3)[!][issue 1999-06].iso/-readerstuff-/paul_qureshi/info/quake.txt

Text File | 1999-03-27 | 10KB | 353 lines

This document contains the transparencies for my talk at the Computer Game Developers Conference on
4/2/96.  Audio and video tapes of the talk are available from the conference organizers.  Note that the
Quake technology described in these transparencies can be licensed from id Software; contact Jay Wilbur
([e-mail]), or Mike Wilson ([e-mail]).
--Michael Abrash






The Quake Graphics Engine


Michael Abrash


id Software



WARNING!
Explicit technical content!!

A highly technical look inside the design of the Quake graphics engine.

1 hour != 12 months

Idea is to give you benefit of our real-world experience to help you up the learning curve.






"Pretty soon, computers will be fast."
                                -Billy Zelsnack



Hardware isn't as fast as we'd like for realtime 3-D, and isn't going to be for a long time.

Hard frame-rate constraints.




Fun thing #1: hardware is fast enough to do interesting things, but not fast enough to do what we really
want.

Fun thing #2: a ton of techniques and approaches, all of which are good for something, none of which are
good for everything.

Balancing act between visual quality and speed, all with the frame rate limit as a hard constraint--and it
all changes every year as hardware moves forward.


Objectives:

Quake:
True, arbitrary 6 DOF 3-D.
Highest possible graphics quality,
   both lighting and rasterizing.
True 3-D for players, monsters, and
   as many objects as possible.

Any 3-D engine:
Correct color at each pixel.
Adequate, reasonably level framerate.

For our purposes, that means sampling the right pixel from the polygon that's nearest at that pixel, and
doing so at 10-15 frame/second minimum.


It would be nice to be able to chuck all the polygons at a rasterizer that was so fast that we didn't have to
think any further.

Problem: no such rasterizer.

Bigger problem: level designers would just use more polygons.

The number of polygons goes up very fast with larger/more complex worlds, much more than linearly,
though the number of visible polygons may not.

Problem of rejecting polygons outside the view pyramid, and frame rate variation.

Principle #1: we need to reduce the polygon set quickly to only those that matter, or at least those that
have a pretty good chance of mattering.

Principle #2: we need to get the right colors on the right pixels for those polygons we do draw; this means
perspective correction, z-ordering, shading, subpixel and subtexel placement, and so on.

#2 has been the focus for a long time, but #1 is quickly becoming the real challenge.  Both must be done
well in order to build a compelling engine



Two parts to the Quake graphics engine:

Static world.

Everything else (moving objects, including players, monsters, doors, platforms, health, ammo, armor, and
so on).

These are handled very differently.



The static world.

Big (up to around 10,000 large polygons), with a continuous polygon mesh skin and any number of light
sources.

Can be preprocessed very effectively.

Is compiled into a single BSP tree.



Handy facts about BSP trees:

Nodes are splitting planes, with polygons stored on them, that carve up space.

Leaves are the convex volumes that nodes carve the world into.

A BSP tree can be walked front-to-back or back-to-front in linear time for any viewpoint.

A BSP tree performs a convex, hierarchical partitioning of space, with each node defining a subspace that
contains all of the node's children.

Hierarchical partitioning helps greatly in large-scale culling.  Node bounding boxes can be clipped to the
view pyramid.

If a node's bounding box is trivially rejected, all its children can be rejected with no further testing.

If a node is trivially accepted, all its children can be accepted with no further testing.


The other part of large-scale culling:  culling polygons that are in the view pyramid but are totally
obscured.
Some of the techniques that were considered and/or tried:

Z-buffering
Painters algorithm
Beam tree
Subdividing raycasting
Edge or span sorting
Portals
Direct visibility extraction from BSP

In every case, some average performance impact, considerable worst-case impact, so frame rate wasn't
very level.




Precalculate the PVS!

Precalculated the PVS from each leaf to each leaf.

Virtually free at runtime.

Very expensive to precalculate--but that's what preprocessing is for.

Speeds up culling to the view pyramid and determination of moving objects that have to be drawn,
because only nodes and leaves in the PVS matter.



Frame rate was still not level enough, because of overdraw.

Added another stage, edge sorting, to process the polygons in the PVS.

Add edges to global table, process all edges at once, top to bottom, emit nearest spans.  Later, draw the
spans for each surface in turn.



Extra sorting work, but reduced overdraw to zero, levelling performance a great deal.

Other benefits:

Shared edges
Concave polygons
Culling of polygons for 3-D hw



What key to sort on?

BSP order.

1/z.

BSP order.

BSPs contain more implicit information that you might think.



Rasterization!

Disadvantages of normal Gouraud shaded texture mapping:

Rotational lighting variance if
   triangles aren't used.

Lighting detail is added by adding
   more polygons.

Lighting is not perspective correct.

Solution: surface caching



Each surface is generated from a combination of a tiled texture and a light map with light values on a 16-
pixel grid.

This is cached and used as the source texture for a non-shading texture mapper.

The light map is precalculated with ray casting from lights to each grid point on each surface.  Radiosity
would be possible.

Per-surface mipmapping helps keep the total cache size down, and also improves appearance at a distance.



Advantages:

No rotational variance.
Perspective correct lighting.
Fewer polgyons.
Lighting separated from polygons.
Ability to post-process.

Disadvantages:

More memory.
More cache misses.
Slow for constantly changing lighting
   (fine for switching lighting on/off).
Slowdown when turning corners.
Not a perfect fit for hardware.



Time to draw!

There's a span drawer that takes the list of spans for a surface and draws the pixels.

No lighting is performed.

The screen gradients for the texture coordinates and 1/z are used to calculate perspective correct texture
coordinates every 8 or 16 pixels, and linear interpolation is used between those points.



100% floating-point down to the 8 or 16 pixel subdivisions.

Hurts on 486, but Pentium floating-point is fast, and floating-point solves all sorts of range and scale
problems, and allows both lowering FDIV precision and overlapping FDIV.  Also, using FP registers frees
up integer registers.

All in all, our inner loop is clearly faster in floating-point on Pentium than it would be in fixed-point



Everything else--moving entities.

There are several types of entities, stored as BSP trees, polygon meshes, sprites, and particles.

Large-scale culling benefits for entities:  Each entity's bounding box is clipped into the world BSP.

Only if it touches a PVS leaf is it flagged for later drawing, after the world has been processed.



Separate BSP models, such as doors, platforms, and health and ammo boxes, are clipped into the world
BSP, then added to the global edge table, just like world polygons.

Doors block view past them, reducing overdraw considerably.

BSP models in the same leaf fall back to sorting against each other on 1/z.



More complex objects, such as torches, armor, and players can't be done with BSPs.

Sprites look startlingly non-3D in a Quake level; they're rare now, and may disappear entirely, but are an
easy solution for objects like torches.

We had been clipping sprites into the world BSP and drawing the pieces by their leaves' BSP order,
drawing back to front.

That approach didn't work so well for polygon models--players and monsters



Polygon models are meshes of 100-400 polygons, with a single front/back skin stretched over them.

We couldn't clip them to the world BSP, because it would be too expensive, so we just drew each triangle
in the nearest leaf it had a vertex in, which caused occasional errors.

Errors sorting polygons within models.

Errors sorting between models in same leaf (and also with other BSP models and sprites).



Tried lots of tweaks (such as putting into edge list), but none was satisfactory until John came up with a
sweeping solution:

Uh... Z-buffering

We z-buffer sprites, polygon models, and all other non-BSP entities.

How low-tech can you get?



Solved all sorting problems for moving entities with NO sorting errors ever.

Fits beautifully into overall design.

Because of no-overdraw spans, can z-fill world at an adequate speed.

Allows post-processing.  At the moment, we're doing particles, scaled NxN colored rectangles, but could
do pretty much anything.

Low-tech, high-tech, whatever; the secret's in the mixing and matching until it all fits


In conclusion:

The more 3-D tricks you know, and the more you experiment, the better.

Yes, I could use a vacation.

Sharing knowledge makes the world a better place.

Further reading:

"Ramblings in Realtime," Dr. Dobb's Sourcebook, 1995-1996.

Zen of Graphics Programming, 2nd ed., the Coriolis Group, April 1996.

Computer Graphics, Foley, van Dam, et al, Addison-Wesley.

Procedural Elements for Computer Graphics, David Rogers, McGraw Hill.